<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>贪吃蛇</title>
    <style type="text/css">
      * {
        margin: 0;
        padding: 0;
        font-family: "Microsoft YaHei";
      }
      #page {
        margin-right: auto;
        margin-left: auto;
        margin-top: 20px;
        height: 680px;
        width: 980px;
      }
      #yard {
        height: 600px;
        width: 900px;
        border: 1px solid gray;
        box-shadow: 0 0 10px black;
        float: right;
      }
      #mark {
        font-weight: 800;
      }
      #mark_con {
        color: red;
      }
      #speed {
        font-weight: 800;
      }
      #speed_con {
        color: red;
      }
      button {
        width: 50px;
      }
      a {
        text-decoration: none;
      }
    </style>
    <script type="text/javascript">
      //常量
      const NEIBOR_NUM_MAX = 4;
      const UP = 0;
      const DOWN = 1;
      const LEFT = 2;
      const RIGHT = 3;

      //伪常量
      var BLOCK_SIZE = 15; //格子大小
      var COLS = 60; //列数
      var ROWS = 40; //行数

      //变量
      var snakes = []; //保存蛇坐标
      var tail; //蛇尾
      var c = null; //绘图对象
      var toGo = 3; //行进方向
      var snakecount = 1; //蛇身数量
      var interval = null; //计时器
      var foodX = 0; //食物X轴坐标
      var foodY = 0; //食物Y轴坐标
      var oMark = null; //分数显示框
      var oSpeed = null; //速度显示框
      var isPause = false; //是否暂停
      async function sleep(ms) {
        return new Promise((resolve) => setTimeout(resolve, ms));
      }

      var AIpath = [];

      //优先队列 https://juejin.cn/post/7045279421334290446
      class PriorityQueue {
        constructor(compare) {
          if (typeof compare !== "function") {
            throw new Error("compare function required!");
          }

          this.data = [];
          this.compare = compare;
          this.length = 0;
        }
        //二分查找 寻找插入位置
        search(target) {
          let low = 0,
            high = this.data.length;
          while (low < high) {
            let mid = low + ((high - low) >> 1);
            if (this.compare(this.data[mid], target) > 0) {
              high = mid;
            } else {
              low = mid + 1;
            }
          }
          return low;
        }
        //添加
        push(elem) {
          // console.log("elem=", elem);
          // console.log("data.length=", this.data.length);
          let index = this.search(elem);
          this.data.splice(index, 0, elem);
          // console.log("data.length=", this.data.length);

          this.length = this.data.length;
          return this.data.length;
        }
        //取出最优元素
        pop() {
          // console.log("this.data=", this.data);
          // console.log("data.length=", this.data.length);

          // for (var i = 0; i < this.data.length; i++) {
          //   console.log("data[", i, "]=", this.data[i]);
          // }
          this.length--;
          return this.data.pop();
        }

        //判断是否为空
        empty() {
          return 0 === this.data.length;
        }
      }
      class Node {
        constructor(x, y) {
          this.x = x;
          this.y = y;
          this.g = 0;
          this.h = 0;
          this.f = 0;
          this.open = false;
          this.close = false;
          this.parent = null;
          this.walkable = true;
        }
        moveToClose() {
          this.open = false;
          this.close = true;
        }
        moveToOpen() {
          this.open = true;
          this.close = false;
        }
      }
      class Map {
        constructor() {
          //创建二维地图,用于规划贪吃蛇路径
          this.mapForAI = new Array(ROWS);
          for (var i = 0; i < ROWS; i++) {
            this.mapForAI[i] = new Array(COLS);
            for (var j = 0; j < COLS; j++) {
              this.mapForAI[i][j] = new Node(j, i); //x是COL,y是ROW,别弄错了
            }
          }

          //初始化不可通行节点
          snakes.forEach((curr) => {
            this.mapForAI[curr.y][curr.x].walkable = false;
          });

          //console.log(this.mapForAI);
        }

        getNeibors(center) {
          var r, c, i;
          var neibors = new Array(NEIBOR_NUM_MAX);

          for (i = 0; i < NEIBOR_NUM_MAX; i++) {
            neibors[i] = null;
          }

          r = center.y;
          c = center.x;

          if (r > 0) neibors[UP] = this.mapForAI[r - 1][c];

          if (r < ROWS - 1) neibors[DOWN] = this.mapForAI[r + 1][c];

          if (c > 0) neibors[LEFT] = this.mapForAI[r][c - 1];

          if (c < COLS - 1) neibors[RIGHT] = this.mapForAI[r][c + 1];

          //console.log(neibors);
          return neibors;
        }
      }

      function abs(x) {
        return x >= 0 ? x : -x;
      }
      function getManhattan(a, b) {
        return abs(a.x - b.x) + abs(a.y - b.y);
      }
      //获取从起点到终点的路径,如果存在则返回路径数组，不存在则返回空数组
      function getPath(src, dst) {
        let havePath = false;
        var path = [];
        var neibors;
        //初始化mapForAI
        map = new Map();

        //构建优先队列
        var openList = new PriorityQueue((n1, n2) => n1.f - n2.f);

        //调用A星算法
        // console.log("src=", src);
        // console.log("dst=", dst);
        var current = map.mapForAI[src.y][src.x];
        // console.log("current=", current);
        openList.push(current);
        current.moveToOpen();
        while (false === openList.empty()) {
          // console.log("openList=", openList);
          current = openList.pop();
          // console.log("current=", current);
          current.moveToClose();

          if (current.x === dst.x && current.y === dst.y) {
            havePath = true;
            break;
          }
          neibors = map.getNeibors(current);
          for (i = 0; i < NEIBOR_NUM_MAX; i++) {
            if (
              null === neibors[i] ||
              false === neibors[i].walkable ||
              true === neibors[i].close
            ) {
              continue;
            }

            if (false === neibors[i].open) {
              neibors[i].g = getManhattan(neibors[i], src);
              neibors[i].h = getManhattan(neibors[i], dst);
              neibors[i].f = neibors[i].g + neibors[i].h;
              neibors[i].moveToOpen();
              neibors[i].parent = current;
              // console.log("neibors[i]=", neibors[i]);
              openList.push(neibors[i]);
              // console.log("openList=", openList);
            } else if (true === neibors[i].open) {
              g = getManhattan(neibors[i], current) + neibors[i].g;
              if (g < neibors[i].g) {
                neibors[i].g = g;
                neibors[i].f = neibors[i].g + neibors[i].h;
                neibors[i].parent = current;
              }
            }
          }
        }

        // console.log("havePath=", havePath);
        //返回路径数组
        if (havePath) {
          current = map.mapForAI[dst.y][dst.x];
          while (null != current.parent) {
            path.unshift(current);
            current = current.parent;
          }
        }
        drawPath(path);

        return path;
      }

      //画路径
      async function drawPath(path) {
        await sleep(1000);
        for (var i = 0; i < path.length; i++) {
          c.beginPath();
          c.fillStyle = "blue";
          c.fillRect(
            path[i].x * BLOCK_SIZE,
            path[i].y * BLOCK_SIZE,
            BLOCK_SIZE,
            BLOCK_SIZE
          );
          c.closePath();
        }
      }
      // 绘图函数
      function draw() {
        c.clearRect(0, 0, BLOCK_SIZE * COLS, BLOCK_SIZE * ROWS);
        //画出横线
        for (var i = 1; i <= ROWS; i++) {
          c.beginPath();
          c.moveTo(0, i * BLOCK_SIZE);
          c.lineTo(BLOCK_SIZE * COLS, i * BLOCK_SIZE);
          c.strokeStyle = "gray";
          c.stroke();
        }
        //画出竖线
        for (var i = 1; i <= COLS; i++) {
          c.beginPath();
          c.moveTo(i * BLOCK_SIZE, 0);
          c.lineTo(i * BLOCK_SIZE, BLOCK_SIZE * ROWS);
          c.stroke();
        }
        //画出蛇
        for (var i = 0; i < snakes.length; i++) {
          c.beginPath();
          c.fillStyle = "green";
          c.fillRect(
            snakes[i].x * BLOCK_SIZE,
            snakes[i].y * BLOCK_SIZE,
            BLOCK_SIZE,
            BLOCK_SIZE
          );
          //绘制边框
          // c.moveTo(snakes[i].x, snakes[i].y);
          // c.lineTo(snakes[i].x + BLOCK_SIZE, snakes[i].y);
          // c.lineTo(snakes[i].x + BLOCK_SIZE, snakes[i].y + BLOCK_SIZE);
          // c.lineTo(snakes[i].x, snakes[i].y + BLOCK_SIZE);
          c.closePath();
          // c.strokeStyle = "white";
          // c.stroke();
        }
        //画出食物
        c.beginPath();
        c.fillStyle = "yellow";
        c.fillRect(
          foodX * BLOCK_SIZE,
          foodY * BLOCK_SIZE,
          BLOCK_SIZE,
          BLOCK_SIZE
        );
        // c.moveTo(foodX, foodY);
        // c.lineTo(foodX + BLOCK_SIZE, foodY);
        // c.lineTo(foodX + BLOCK_SIZE, foodY + BLOCK_SIZE);
        // c.lineTo(foodX, foodY + BLOCK_SIZE);
        c.closePath();
        // c.strokeStyle = "red";
        // c.stroke();
      }
      //游戏初始化
      function start() {
        for (var i = 0; i < snakecount; i++) {
          snakes[i] = { x: i, y: 0 };
        }
        addFood();
        draw();
        oMark.innerHTML = 0; //分数初始为 0
        speed = 10; //速度初始为 10
        oSpeed.innerHTML = speed.toString();
      }

      //AI移动函数
      function AImove() {
        var food = { x: 0, y: 0 };
        food.x = foodX;
        food.y = foodY;
        if (0 === AIpath.length) {
          head = snakes[snakecount - 1];
          AIpath = getPath(head, food);
          // console.log("AIPath=", AIpath);
        }
        next = AIpath.shift();
        snakes.push({ x: next.x, y: next.y });
        tail = snakes.shift(); //shift() 方法用于把数组的第一个元素从其中删除，并返回第一个元素的值
        isEat();
        isDie();
        draw();
      }
      //吃到食物判断
      function isEat() {
        head = snakes[snakecount - 1];
        if (head.x == foodX && head.y == foodY) {
          oMark.innerHTML = (parseInt(oMark.innerHTML) + 1).toString(); //分数+1
          addFood(); //新增食物
          addSnake(); //蛇身长度+1
        }
      }
      //添加蛇身
      function addSnake() {
        snakecount++;
        snakes.unshift(tail); //unshift() 方法可向数组的开头添加一个或更多元素，并返回新的长度
      }
      //交互响应函数
      function keydown(keyCode) {
        switch (keyCode) {
          case 37: //左边
            if (toGo != 1 && toGo != 3) toGo = 1;
            break;
          case 38: //上边
            if (toGo != 2 && toGo != 4) toGo = 2;
            break;
          case 39: //右边
            if (toGo != 3 && toGo != 1) toGo = 3;
            break;
          case 40: //下的
            if (toGo != 4 && toGo != 2) toGo = 4;
            break;
          case 80: //开始/暂停
            if (isPause) {
              interval = setInterval(move, 100);
              isPause = false;
              document.getElementById("pause").innerHTML = "P暂停";
            } else {
              clearInterval(interval);
              isPause = true;
              document.getElementById("pause").innerHTML = "P开始";
            }
            break;
          case 81: //速度增加
            speed += 1;
            oSpeed.innerHTML = speed.toString();
            clearInterval(interval);
            interval = setInterval(AImove, 1000 / speed);
            break;
          case 82: //速度降低
            speed -= 1;
            oSpeed.innerHTML = speed.toString();
            clearInterval(interval);
            interval = setInterval(AImove, 1000 / speed);
            break;
        }
      }
      //制造食物
      function addFood() {
        foodX = Math.floor(Math.random() * (COLS - 1));
        foodY = Math.floor(Math.random() * (ROWS - 1));
        // console.log(foodX + " -- " + foodY);
      }
      //死亡判断
      function isDie() {
        head = snakes[snakecount - 1];
        if (head.x < 0 || head.x == COLS || head.y < 0 || head.y == ROWS) {
          alert("撞墙死亡");
          clearInterval(interval);
        }
        for (var i = 0; i < snakecount - 1; i++) {
          if (head.x == snakes[i].x && head.y == snakes[i].y) {
            clearInterval(interval);
            alert("撞自己死亡");
          }
        }
      }
      // 启动函数
      window.onload = function () {
        c = document.getElementById("canvas").getContext("2d");
        oMark = document.getElementById("mark_con");
        oSpeed = document.getElementById("speed_con");
        oSpeed.innerHTML = speed.toString();
        start();
        interval = setInterval(AImove, 1000 / speed); //每1000/speed 调用一次 move
        document.onkeydown = function (event) {
          var event = event || window.event;
          keydown(event.keyCode);
        };
      };
    </script>
  </head>
  <body>
    <div id="page">
      <div id="yard">
        <canvas id="canvas" height="600px" width="900px"></canvas>
      </div>
      <div id="help">
        <div id="mark">得分：<span id="mark_con"></span></div>
        <div id="speed">
          速度: <span id="speed_con"></span>
          <table>
            <tr>
              <td><button onclick="keydown(81);">+</button></td>
            </tr>
            <tr>
              <td><button onclick="keydown(82);">-</button></td>
            </tr>
          </table>
        </div>
      </div>
    </div>
    <div style="text-align: center">
      <div id="helper">
        <a href="index.html">再玩一次</a><span></span>
        <a href="indexManual.html">再玩一次(手动版)</a>
      </div>
      <p>作者: 小白菜</p>
    </div>
  </body>
</html>
